package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-03
 * Time:15:56
 */

import java.util.Stack;

/**
 *
 牛客算法篇:BM33 二叉树的镜像
 描述
 操作给定的二叉树，将其变换为源二叉树的镜像。
 数据范围：二叉树的节点数 0≤n≤10000≤n≤1000 ， 二叉树每个节点的值 0≤val≤10000≤val≤1000
 要求： 空间复杂度 O(n)O(n) 。本题也有原地操作，即空间复杂度 O(1)O(1) 的解法，时间复杂度 O(n)O(n)
 比如：
 源二叉树
 镜像二叉树
 示例1
 输入：
 {8,6,10,5,7,9,11}
 返回值：
 {8,10,6,11,9,7,5}
 说明：
 如题面所示
 */
public class Mirror {

    public TreeNode Mirror (TreeNode root) {
        // write code here
        if(root == null) return root;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (stack.isEmpty()){
            TreeNode cur = stack.pop();
            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right = tmp;
            if (cur.left != null){
                stack.push(cur.left);
            }
            if (cur.right != null){
                stack.push(cur.right);
            }
        }
        return root;
    }

}
